Data storage devices often use a static logical-to-physical mapping because static mappings can be driven by small and efficient tables and equations. Dynamic logical-to-physical mappings are an attractive alternative to static mappings, especially for data storage media such as NAND Flash or shingled magnetic recording (SMR) media that require or benefit from sequential writing and re-use of storage units such as erasure blocks or bands of tracks. Dynamic mappings, however, can require complicated tables that require compromises among memory size, search time, insertion time deletion time, write throughput and other factors when handling random access workloads.